package com.felix.algorithms.sort;

import java.util.Arrays;

/**
 * Sort
 *
 * @author xuejinhua
 * @date 2018/10/29 14:13
 */
public class Sort {

    /**
     * 简单选择排序
     *
     * @param arr
     */
    public static void selectSort(Integer[] arr) {

        for (int i = 0; i < arr.length - 1; i++) {
            //每一趟循环比较时，min用于存放较小元素的数组下标，这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标，避免每次遇到较小元素都要进行交换。
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            //进行交换，如果min发生变化，则进行交换
            if (min != i) {
                swap(arr, min, i);
            }
        }
    }

    /**
     * 插入排序
     *
     * @param arr
     */
    public static void insertionSort(Integer[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (j > 0 && arr[j] < arr[j - 1]) {
                swap(arr, j, j - 1);
                j--;
            }
        }
    }

    /**
     * 交换数组元素
     *
     * @param x
     * @param a
     * @param b
     */
    public static void swap(Object[] x, int a, int b) {
        Object t = x[a];
        x[a] = x[b];
        x[b] = t;
    }

    private static final int INSERTIONSORT_THRESHOLD = 7;

    private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low,
                                  int high,
                                  int off) {
        int length = high - low;

        // Insertion sort on smallest arrays
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i = low; i < high; i++) {
                for (int j = i; j > low &&
                        ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--) {
                    swap(dest, j, j - 1);
                }
            }
            return;
        }

        // Recursively sort halves of dest into src
        int destLow = low;
        int destHigh = high;
        low += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (((Comparable) src[mid - 1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // Merge sorted halves (now in src) into dest
        for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable) src[p]).compareTo(src[q]) <= 0) {
                dest[i] = src[p++];
            } else {
                dest[i] = src[q++];
            }
        }
    }

    public static void main(String[] args) {
        Integer[] src = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
        Integer[] dest = new Integer[10];
        merge(src, dest, 0, 10);
        System.out.println(Arrays.toString(dest));
    }

    private static void merge(Integer[] src, Integer[] dest, int low, int high) {
        int length = high - low;
        if (length < 7) {
            for (int i = low; i < high; i++) {
                for (int j = i; j > low && dest[j - 1] > dest[j]; j--) {
                    swap(dest, j, j - 1);
                }
            }
            return;
        }
        int mid = (low + high) >>> 1;
        merge(dest, src, low, mid);
        merge(dest, src, mid, high);
        if (src[mid - 1] <= src[mid]) {
            System.arraycopy(src, low, dest, low, length);
            return;
        }
        for (int i = low, p = low, q = mid; i < high; i++) {
            if (q >= high || p < mid && src[p] <= src[q]) {
                dest[i] = src[p++];
            } else {
                dest[i] = src[q++];
            }
        }
    }

    public static void insertSort(Integer[] dest) {
        for (int i = 0; i < dest.length; i++) {
            for (int j = i; j > 0 && dest[j - 1] > dest[j]; j--) {
                swap(dest, j, j - 1);
            }
        }
    }


}
